package com.kaizen.leet437;

import jdk.nashorn.internal.ir.BinaryNode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 *
 * 437. 路径总和 III
 * 给定一个二叉树，它的每个结点都存放着一个整数值。
 *
 * 找出路径和等于给定数值的路径总数。
 *
 * 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 *
 * 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
 *
 * 示例：
 *
 * root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
 *
 *       10
 *      /  \
 *     5   -3
 *    / \    \
 *   3   2   11
 *  / \   \
 * 3  -2   1
 *
 * 返回 3。和等于 8 的路径有:
 *
 * 1.  5 -> 3
 * 2.  5 -> 2 -> 1
 * 3.  -3 -> 11
 *
 * 解题思路：
 * 1.重递归的操作，这种题目需要从每个节点开始进行类似的计算，所以第一个递归用来遍历这些节点，这二个递归用来处理这些节点，进行深度优先搜索。
 * 2.此题还有时间复杂度为O(n)的解法，n为树的节点数，
 * 用的方法是前缀和，遍历到某个节点时，在hash中查找前缀和为prefix_sum-sum的节点的个数，
 * 结果等于这个个数加上左右子树中满足条件的节点个数
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/path-sum-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author kaizen
 * @date 2020/5/17 19:06
 *
 */
public class SolutionKaizen {


    /**
     * 所以第二种做法，采取了类似于数组的前n项和的思路，比如sum[4] == sum[1]，那么1到4之间的和肯定为0
     *
     * 对于树的话，采取DFS加回溯，每次访问到一个节点，把该节点加入到当前的pathSum中
     * 然后判断是否存在一个之前的前n项和，其值等于pathSum与sum之差
     * 如果有，就说明现在的前n项和，减去之前的前n项和，等于sum，那么也就是说，这两个点之间的路径和，就是sum
     *
     * 最后要注意的是，记得回溯，把路径和弹出去
     *
     * 作者：a380922457
     * 链接：https://leetcode-cn.com/problems/path-sum-iii/solution/liang-chong-fang-fa-jian-dan-yi-dong-ban-ben-by-a3/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param root
     * @param sum
     * @return
     */
    public int pathSum(TreeNode root, int sum) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        //设置路径和符合条件即res+1的前提（0=pathSum-sum）
        map.put(0, 1);
        return helper(root, map, sum, 0);
    }

    int helper(TreeNode root, HashMap<Integer, Integer> map, int sum, int pathSum){
        if(root == null) return 0;
        int res = 0;
        //将当前所在节点的值加到走过的路径值的和中
        pathSum += root.val;
        //getOrDefault(Object key,V defaultValue)
        // 以上方法为返回指定键（Object key）所映射的值，若无则直接返回所设置的默认值（V defaultValue）
        //累加上到当前节点为止有多少条路径和符合条件（此处若是pathSum-sum==0,则返回1，在map中若存在当前pathSum-sum对应值
        //的key则对应value的值则必不为0，为1或大于1，若无此key则返回方法默认值0）
        res += map.getOrDefault(pathSum - sum, 0);
        //此处是计数到当前节点为止有多少条自上而下的节点路径和等于pathSum，并将其存入map
        // （亦或是更新pathSum对应的路径数，若先前有和值为pathSum的路径则取出其条数先前加上当前的一条）
        map.put(pathSum, map.getOrDefault(pathSum, 0) + 1);
        //往左子树以及右子树依次统计
        // 再加上res-->到当前节点为止可能出现的和值符合pathSum的路径数（统计范围即为头节点到当前节点）
        res = helper(root.left, map, sum, pathSum) + helper(root.right, map, sum, pathSum) + res;
        // 在返回前，将到当前节点为止的和值pathSum的条数计-1，防止影响后面其他未走完路径的统计
        //由于路径和值只能自上而下，所以在当前节点返回前（节点返回条件为下一节点为空，
        // 即为最后节点或者最后节点返回后遍历完依次往上递归返回，返回意味着pathSum到当前节点已自上而下的累加遍历完）
        map.put(pathSum, map.get(pathSum) - 1);
        return res;
    }

    /**
     *
     * @param root
     * @param sum
     * @return
     */
    public int pathSum2(TreeNode root, int sum) {
        return pathSum2(root, sum, 0, new int[1000]);
    }

    /**
     *
     * @param root
     * @param sum
     * @param level
     * @param pathArr
     * @return
     */
    private int pathSum2(TreeNode root, int sum, int level,int[] pathArr){
        if(root == null) {
            return 0;
        }
        pathArr[level] = root.val;
        int n = 0;
        int tmpSum = 0;
        for(int i=level;i>=0;i--){
            tmpSum+=pathArr[i];
            if(tmpSum == sum) {
                n++;
            }
        }
        return n+pathSum2(root.left,sum,level+1,pathArr)+pathSum2(root.right,sum,level+1,pathArr);
    }

    /**
     * DFS
     * 。这就要求我们只需要去求三部分即可：
     *
     * 以当前节点作为头结点的路径数量
     * 以当前节点的左孩子作为头结点的路径数量
     * 以当前节点的右孩子作为头结点啊路径数量
     * 将这三部分之和作为最后结果即可。
     *
     * 作者：ming-zhi-shan-you--m9RfkvKDad
     * 链接：https://leetcode-cn.com/problems/path-sum-iii/solution/437lu-jing-zong-he-iii-di-gui-fang-shi-by-ming-zhi/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param root
     * @param sum
     * @return
     */
    public int pathSum1(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        int result = countPath(root,sum);
        int a = pathSum1(root.left,sum);
        int b = pathSum1(root.right,sum);
        return result+a+b;
    }

    /**
     * 最后的问题是：我们应该如何去求以当前节点作为头结点的路径的数量？这里依旧是按照树的遍历方式模板，每到一个节点让sum-root.val，并判断sum是否为0，如果为零的话，则找到满足条件的一条路径。
     *
     * 作者：ming-zhi-shan-you--m9RfkvKDad
     * 链接：https://leetcode-cn.com/problems/path-sum-iii/solution/437lu-jing-zong-he-iii-di-gui-fang-shi-by-ming-zhi/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param root
     * @param sum
     * @return
     */
    public int countPath(TreeNode root,int sum){
        if(root == null){
            return 0;
        }
        sum = sum - root.val;
        int result = sum == 0 ? 1:0;
        return result + countPath(root.left, sum) + countPath(root.right, sum);
    }


}
